package algorithm_demo.demo03;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 是否为完全二叉树
 * 1. 任何节点，有右节点无左节点，返回false，否则，继续
 * 2. 一旦遇到左右孩子不双全，后续遇到的所有节点必须是叶子节点
 *
 * @author Api
 * @date 2023/2/12 17:17
 */
public class Code06_IsCBT {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    //非递归，按层遍历
    public static boolean isCBT1(Node head) {
        if (head == null) {
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        //是否遇到过左右两个不双全的节点
        boolean leaf = false;
        Node l = null;
        Node r = null;
        queue.add(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            l = head.left;
            r = head.right;
            //如果遇到不双全的节点之后，又发现当前节点不是叶子节点
            //leaf && (l != null || r != null)  条件二
            //(l == null && r != null)  条件一
            if (leaf && (l != null || r != null) || (l == null && r != null)) {
                return false;
            }
            if (l != null) {
                queue.add(l);
            }
            if (r != null) {
                queue.add(r);
            }
            if (l == null || r == null) {//第一次不双全时，设置为true
                leaf = true;
            }
        }
        return true;
    }


}
